package ljl.alg.jianzhioffer.round2;

public class _62_last_number_in_circle {
    
    /**
     * 原问题是序列 0 1 2 3 ... n - 1
     * 子问题是序列 0 1 2 3 ... n - 2
     *
     * 原始问题的解是 f(n)，删除的数字是 (m - 1) % n
     * 子问题的解是 f(n - 1)，子问题从下一个数字开始，设为 t = m % n
     *      0  0 + t
     *      1  1 + t
     *      2  2 + t
     *      ...
     *      n - 2 n - 2 + t
     *
     * f(n) 中的数字 x，对应 f(n - 1) 里的 (x + t) % n = (x + m % n) % n = (x + m) % n
     * 这样可以根据 f(n - 1) 推出 f(n) 了
     * 而 f(1) = 0
     * 从 2 循环到 n 就可以获得 f(n) 的解
     *
     * */
    public int lastRemaining(int n, int m) {
        int res = 0;
        // 错了好几处
        // 1. res 从 0 开始，f(1) = 0
        // 2. i 从 2 开始，到 n 结束，因为是从第二轮开始，第一轮结果已知
        // 3. 每次应该对 i 取余，因为每轮都是要对长度取余，而 i 就是长度
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }
    
    /**
     * 操你妈辛辛苦苦写了一个小时超时了
     * */
    static class timeout {
        // 0 1 2 3 4 - 3
        // 搞个链表试试吧。。
        public int lastRemaining(int n, int m) {
            class Node {
                int val;
                Node next;
            }
            Node head = new Node();
            Node p = head;
            for (int i = 0; i < n; i++) {
                p.next = new Node();
                p.next.val = i;
                p = p.next;
            }
            p.next = head.next;
        
            // 0 1 2 3 4 - 2
            Node prev = head;
            p = head.next;
            int count = n;
            while (count > 1) {
                int t = m;
                while (t-- > 1) {
                    prev = p;
                    p = p.next;
                }
                prev.next = p.next;
                //System.out.println(p.val);
                p = p.next;
                count--;
            }
            return p.val;
        }
    }
    
    
    
}
